
public class Tp2_Ej2_Main {

	public static void main(String[] args) {
		String nombreArchivo = "Tp2";
		
		String archivoEntrada = ".\\resources\\" + nombreArchivo + "Ej2.in";
		String archivoSalida = ".\\resources\\" + nombreArchivo + "Ej2.out";
		String archivoTiempos = ".\\resources\\" + nombreArchivo + "Ej2.time";
		
		algoritmo(archivoEntrada, archivoSalida, archivoTiempos);
		
	}
	private static void algoritmo(String archivoEntrada, String archivoSalida, String archivoTiempos) {
		FileParser fp = new FileParser(archivoEntrada);
		FileWriter fw = new FileWriter(archivoSalida);
		FileWriter fwTiempos = new FileWriter(archivoTiempos);
		
		//peorCaso(archivoEntrada);
		//mejorCasoBis(archivoEntrada);
		int cantidadRepeticiones=5;
		long minMedicion=0;
		boolean res = true;
		
		while (!fp.getLine().trim().equals("-1")) {
			Grafo instancia = parsearInstancia(fp);
			for (int rep=0 ;rep<cantidadRepeticiones;rep++) {
				long tiempoInicio = System.nanoTime();
				res = esFuertementeConexo(instancia);
				
				long totalTiempo = System.nanoTime()- tiempoInicio;
				minMedicion+=totalTiempo;
			}
			minMedicion /= cantidadRepeticiones;
			fwTiempos.writeLine(instancia.getMaxVertices() + " " + String.valueOf(minMedicion));
			System.out.println("El resultado de la instancia es: " + res);
			
			if (res)
				fw.writeLine("fuertemente conexo");
			else
				fw.writeLine("no");
		}
		
		fw.closeFile();
		fp.closeFile();
		fwTiempos.closeFile();
	}

	private static void mejorCaso(String archivoSalida){
		FileWriter fw = new FileWriter(archivoSalida);
		String cadena="";
		for (int numMatriz=9;numMatriz<200;numMatriz+=2 ){
			int matriz[][]=new int[numMatriz][numMatriz];
			fw.writeLine(String.valueOf(numMatriz));

			for(int i =0;i <numMatriz;i++){
				for (int j=0;j<numMatriz;j++){
					matriz[i][j]=-1;
				}
			}
			for(int i =0;i <numMatriz;i++){
				if ((i>0) && (i<numMatriz-1)){
					matriz[i][i-1]=i-1;
					matriz[i][i+1]=i+1;
				}else
				if(i==0){
					matriz[0][numMatriz-1]=numMatriz-1;
					matriz[0][1]=i+1;
				}else
				if(i==numMatriz-1){
					matriz[i][0]=0;
					matriz[i][i-1]=i-1;
				}
					

			}
			for (int i=0;i<numMatriz;i++){
				cadena+= 2 + " ";
				for (int j=0;j<numMatriz;j++){
					if (matriz[j][i]>=0){
						cadena+= matriz[i][j] + " ";
					}
				}
				fw.writeLine(cadena);
				cadena="";
			}
			
		}
		fw.writeLine("-1");
		fw.closeFile();
		
	}

	private static void mejorCasoBis(String archivoSalida){
		FileWriter fw = new FileWriter(archivoSalida);
		String cadena="";
		for (int numMatriz=9;numMatriz<200;numMatriz+=2 ){
			int matriz[][]=new int[numMatriz][numMatriz];
			int vector[] = new int[numMatriz];
			fw.writeLine(String.valueOf(numMatriz));

			for(int i =0;i <numMatriz;i++){
				for (int j=0;j<numMatriz;j++){
					matriz[i][j]=-1;
				}
			}
			for (int i=1; i < numMatriz; i+=2){
				
//				matriz[i-1][i-1]	=i-1;
				matriz[i-1][i]		=i-1;
				matriz[i-1][i+1]	=i-1;
				vector[i-1]++;
				vector[i-1]++;

				matriz[i][i-1]		=i;
//				matriz[i][i]		=i;
				matriz[i][i+1]		=i;
				vector[i]++;
				vector[i]++;

				matriz[i+1][i-1]	=i+1;
				matriz[i+1][i]		=i+1;
//				matriz[i+1][i+1]	=i+1;
				vector[i+1]++;
				vector[i+1]++;
			}
			
					
			for (int i=0;i<numMatriz;i++){
				cadena+= vector[i] + " ";
				for (int j=0;j<numMatriz;j++){
					if (matriz[j][i]>=0){
						int a = matriz[j][i] ;
						cadena+= a + " ";
					}
				}
				fw.writeLine(cadena);
				cadena="";
			}
			
		}
		fw.writeLine("-1");
		fw.closeFile();
		
	}

	
	
	private static void peorCaso(String archivoSalida){
		FileWriter fw = new FileWriter(archivoSalida);
		String cadena="";
		for (int numMatriz=9;numMatriz<200;numMatriz+=2 ){
			int matriz[][]=new int[numMatriz][numMatriz];
			int grados[]=new int[numMatriz];
			for(int i =0;i <numMatriz;i++){
				for (int j=0;j<numMatriz;j++){
					matriz[i][j]=-1;
				}
			}
			fw.writeLine(String.valueOf(numMatriz));
			for (int i=0;i<numMatriz/2;i++){
				for (int j=i;j<numMatriz;j++){
					int valori=-1;
					int valorj=-1;
					if (j==i+1){
						valori=i;
						valorj=j;
						grados[i]++;
						grados[j]++;
					}
					else if (j == numMatriz-i-1){
						valori=i;
						valorj=j;
						grados[i]++;
						grados[j]++;
					}
					matriz[i][j]=valori;
					matriz[j][i]=valorj;

				}
			}
			for (int i=0;i<numMatriz-1;i++){
				matriz[i+1][numMatriz-(i+1)]=i+1;
				grados[i+1]++;
			}
			
			
			for (int i=0;i<numMatriz;i++){
				cadena+=grados[i] + " ";
				for (int j=0;j<numMatriz;j++){
					if (matriz[j][i]>=0){
						cadena+= matriz[j][i] + " ";
					}
				}
				fw.writeLine(cadena);
				cadena="";

			}
			
		}
		fw.writeLine("-1");
		fw.closeFile();
	}
	
	
	private static Grafo parsearInstancia(FileParser fp) {
		Integer id = 0;
		
		String[] str = fp.getLine().trim().replaceAll("\\s+", " ").split("\\s");
		int cantVertices = (Integer.parseInt(str[0]));
		Grafo g = new Grafo(cantVertices);
		
		fp.nextLine();

		while (id <= cantVertices-1){
			String[] str2 = fp.getLine().trim().replaceAll("\\s+", " ").split("\\s");
			int cantAmigosActual = Integer.parseInt(str2[0]);
			int i = 0;
			
			while (i <= cantAmigosActual-1){
				g.agregaEje(id, Integer.parseInt(str2[i+1])-1);
				i++;
			}
			
			fp.nextLine();
			id++;
		}

		return g;
	}

	

	private static boolean esFuertementeConexo(Grafo g) {
		int circuitoSimple[]		= new int[g.getMaxVertices()];
		int listaVisitadosConDfs[] 	= new int[g.getMaxVertices()];
		int bolsa[]					= new int[g.getMaxVertices()];
		Pila laPila					= new Pila(g.getMaxVertices());
		int cantElementosEnBolsa 	= 0; 

// Comenzamos en el primer vertice.
		listaVisitadosConDfs[0] = 1; 					// Lo marcamos.
		bolsa[0] = 1; 									//pongo el primer elemento en la bolsa
		cantElementosEnBolsa++;
		circuitoSimple[0] = 1; 							// Lo marcamos.
		laPila.push(0); 								// Lo apilamos.
		int anterior = 0; 								//me guardo de donde vengo
		
		while(!laPila.vacio()) { 						// Hasta que la pila no sea vacia.

// Tomamos un vertice no visitado adyacente al tope de la pila.
			int v = getVerticesNoVisitados(g,laPila.peek(),listaVisitadosConDfs);
			if(v == -1) { 								// Si no hay tal vertice.
				circuitoSimple[laPila.peek()] = 0;
				laPila.pop(); // Lo desapilamos.
				if (!laPila.vacio())
					anterior=laPila.peek();
			}
			else { // Sino, si existe.
				listaVisitadosConDfs[v]=1; 			// Lo marcamos.
				circuitoSimple[v] = 1; 				// Lo marcamos.

				if(hayCiclo(g,v,anterior,bolsa)==1){ //verifica si hay ciclo
//recorro,pinto y pongo vector en 0
					
					for (int i = 0 ;i<g.getMaxVertices();i++  ){
						if (bolsa[i]==0 && circuitoSimple[i]==1){
							bolsa[i]= 1;
							cantElementosEnBolsa++;
						}
						if (circuitoSimple[i]==0 && bolsa[i]==0){
							listaVisitadosConDfs[i]=0;// despinto el dfs!! para un caso particular.
						}
						circuitoSimple[i]=0;
						
					}
					if(g.getMaxVertices() == (cantElementosEnBolsa)){
						return true;
							
					}
				}

			anterior=v;
			laPila.push(v); // Lo apilamos.
			}
		
		}
		return false;

	}
		
	public static int getVerticesNoVisitados(Grafo g,int v,int listaVisitadosConDfs[]) {
// recorre la matriz de adjacencia y devuelve algun vertice que sea posible visitar.
		for(int j=0; j<g.getMaxVertices(); j++)
		{
			if(g.estaEnMatAdj(v, j)==1 && listaVisitadosConDfs[j]==0)
				return j;
		}
		return -1;
	}

	public static int hayCiclo(Grafo g,int v,int anterior,int bolsa[]) {
// recorre la matriz de adjacencia y pregunta si el vertice v esta relacionado 
// con los elementos de la bolsa excluyendo al vertice de donde viene
		
		for(int j=0; j<g.getMaxVertices(); j++)
			if (j!= anterior) {
				if(g.estaEnMatAdj(v, j)==1 && bolsa[j]==1)
					return 1;// se relaciona con alguno de la bolsa y esta en la matriz de adj
			}
			return 0;
	}

}
